home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Interactive Reference Guide / C-C++ Interactive Reference Guide.iso / c_ref / csource3 / 103_01 / pkunpk.doc < prev    next >
Encoding:
Text File  |  1985-03-11  |  7.0 KB  |  187 lines
  1. 20 MAY 81 by Kathy Bacon who is going to spend the rest of her 
  2.                 life documenting her (and others) programs..... 
  3.  
  4. DOCUMENTATION FOR PACK - UNPACK SET OF PROGRAMS USING THE 
  5.         HOFFMAN MINIMUM REDUNDANCY ALGORITHM 
  6.  
  7.  
  8.         The  program  PACK can be used to "pack" or encode a file into
  9. a form that requires less storage;  the  original  file  can  then  be
  10. gotten back by running it through UNPACK. 
  11.         Put  quite  simply,  PACK  reads through the file to be packed
  12. and counts the number of times each  character  in  the  file  occurs.
  13. Using  this information, it constructs a tree structure, which it then
  14. uses to generate a bit code for every character which appears  in  the
  15. file,  in  such  a  way that the characters which appear the most have
  16. the codes with the fewest bits, and those that appear less often  have
  17. longer  codes  (e.g.  the  character which appears the most often will
  18. have the bit code (0) or (1); the  next  group  will  have  the  codes
  19. (00),(01),  (10),(11),  etc.). It then writes out the file using these
  20. codes instead of the characters themselves; the  character  occurrence
  21. infor- mation is stored in the first four sectors of the new file. 
  22.         UNPACK  reads  the  occurrence information from a packed file,
  23. reconstructs the tree,  regenerates  the  codes  from  the  tree,  and
  24. finally  translates  the  bit  codes  in the packed file back to their
  25. character equivilents. 
  26.         Both PACK and UNPACK can accept more  than  one  command  line
  27. argument  at a time to be packed or unpacked. Also, a destination file
  28. can be specified like so: 
  29.  
  30.         A>pack source>destin 
  31.  
  32. There should be NO spaces  between  the  file  names  and  the  output
  33. specifier  '>'.  If  no destination file is specified, the output file
  34. from PACK will be source.PAK ; source.UNP from UNPACK. 
  35.  
  36.                 $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ 
  37.         Note: any type of file can be packed. The more random  a  file
  38. is  the  less the savings will be. Best savings occur on text files. C
  39. com files offer less and assembly language com files even  less.  Even
  40. previously  packed files can be packed and sometimes there can be some
  41. savings (not all the time though). Of course you would have to  unpack
  42. it  twice  to get back the original. Work is in progress on shortening
  43. overhead of the character occurrence information. We have  packed  and
  44. unpacked  many  files  and  the programs seem to be fairly robust. Try
  45. unpacking files that are not packed. (GIGO). Savings  for  text  files
  46. are  typically  on the order of 30%, for com files more like 20%. Have
  47. fun and save space. 
  48.                 $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ 
  49.  
  50.         The "tree" is actually an array of  elements  (512  in  all  -
  51. twice  the possible number of character types), each of which has four
  52. parts: 
  53.  
  54.         1) the character occurrence value for that element 
  55.  
  56.         2) a pointer to a son (called "son_zero") 
  57.  
  58.         3) a pointer to a second son ("son_one") 
  59.  
  60.         4) a pointer to the element's "daddy" 
  61.  
  62. The first 256 array elements are the characters - each index into  the
  63. array  is  the  numerical equivelent of some character. Initially, all
  64. of the pointers are set to NIL  (-1  in  this  case);  all  occurrence
  65. fields  are  set to zero. Then the occurrence information is filled in
  66. for the first 256 elements (in PACK this  is  done  by  actully  going
  67. through  the  file;  in  UNPACK the information is read from the first
  68. four sectors of the file ). 
  69.  
  70.                 &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 
  71.  
  72. The same function is used to  generate  the  tree  in  both  PACK  and
  73. UNPACK.  A  pointer  to the tree structure is passed to it; it returns
  74. the number of the "head" of the tree, when it's done: 
  75.  
  76. { 
  77. daddy = NIL; 
  78. nextpapa = number of char types (256) 
  79.  
  80. while(1) 
  81.       { 
  82.         find the two elements in the tree with the lowest occur. 
  83.         values. Label one ONE, the other ZERO. 
  84.  
  85.         if (both ONE and ZERO are NIL) 
  86.                 return the current daddy 
  87.  
  88.         if (ONE == NIL) 
  89.                 return the value of ONE 
  90.  
  91.         daddy = nextpapa 
  92.         nextpapa = nextpapa + 1 
  93.  
  94.         set the pointer "son_zero" at element "daddy" to ZERO; 
  95.         set the pointer "son_one" at element "daddy" to ONE 
  96.  
  97.         set the pointers to "dad" at elements ONE and ZERO to 
  98.                 "daddy" 
  99.  
  100.         the occurrence value at element "daddy" is the sum of 
  101.         the occur. values at elements ONE and ZERO 
  102.  
  103.       } 
  104. } 
  105.  
  106. This will generate a tree in which all  the  "leaves"  are  characters
  107. (elements  0-255  in the tree array); no character will have a son_one
  108. or a son_zero. 
  109.  
  110.                 $$$$$$$$$$$$$$$$$$$$$$$$$$$$$ 
  111.  
  112. Once the tree has  been  generated,  and  the  occurrence  information
  113. written  out  to  the  output  file, PACK uses the occurrence field at
  114. each element on the tree to tell whether that element in  a  "son_one"
  115. or  "son_zero"  of  its  "dad". This simplifies the encoding, which is
  116. done as follows: 
  117.  
  118.  
  119. { 
  120. while (more characters in input) 
  121.       { 
  122.         get a character 
  123.  
  124.         starting at the character's element in the tree, read off 
  125.                 the element's occur. value into a stack; then go to 
  126.                 it's "dad" and do likewise. Continue until you find 
  127.                 an element whose "dad" is NIL. This is the head of 
  128.                 the tree. 
  129.  
  130.         read the bits back off the stack (reverse of the way they 
  131.                 went in) one at a time, shoving them into an output 
  132.                 byte. When there are eight in the byte, put it into 
  133.                 the output buffer and start over with a new byte. If 
  134.                 the output buffer is full, write it out to the file. 
  135.  
  136.       } end while (more input characters) 
  137.  
  138. if (there's part of an output byte left) 
  139.       { 
  140.         put it in the buffer 
  141.         write out the buffer to the file 
  142.       } 
  143.  
  144. } 
  145.  
  146.         $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ 
  147.  
  148. To pack a file, we start at the "leaves" of the tree (at a  character)
  149. and  follow  the  "dad"s up to the "big_daddy" of the tree to generate
  150. the bit codes; to unpack, we do the reverse: we start at the  head  of
  151. the  tree  and  follow  the  bit  code  down the pointers (following a
  152. son_one if the bit is a one, a son_zer if it's a zero) until we  reach
  153. a character: 
  154.  
  155. { 
  156. calculate the number of characters that were in the unpacked file 
  157.  
  158. while (no. decoded chars < no. in original file) 
  159.       { 
  160.         get a byte from the packed file 
  161.  
  162.         for (i=1 to 8) 
  163.         { get a bit 
  164.                 if (bit==0) 
  165.                         go to current element's son_zero 
  166.                 else go to son_one 
  167.  
  168.                 if (new element is a character) 
  169.                 { put character in output buffer 
  170.  
  171.                         write out buffer if it's full 
  172.  
  173.                         reset element to "big_daddy" 
  174.                 } 
  175.         } 
  176.       } 
  177. if (part of a buffer done) 
  178.         write out buffer to file 
  179. } 
  180.  
  181.  
  182.  
  183.  
  184.  
  185.  
  186.  
  187. tree